package com.liuwei.spring.cloud.junit.leetcode.dp;

import lombok.extern.slf4j.Slf4j;
import org.apache.commons.collections4.CollectionUtils;

/**
 * https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked
 */
@Slf4j
public class CoinChange {
    /***
     * 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额
     * 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1
     * 你可以认为每种硬币的数量是无限的
     */
    public static void main(String[] args) {
        CoinChange solution = new CoinChange();
        int amount = 11;
        int[] coins = new int[]{1,2,5};
        int result = solution.coinChange(coins,amount);
        log.info("result:{}",result);
    }

    /**
     * 最优决策表 = 一维表
     * @param coins
     * @param amount
     * @return
     */
    public int coinChange(int[] coins, int amount) {
        // 自底向上的动态规划
        if(coins.length == 0){
            return -1;
        }

        // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
        // 需包含 amount = 0 的情况, size = amount +1;
        int[] memo = new int[amount+1];
        memo[0] = 0;
        for(int i = 1; i <= amount;i++){
            int min = Integer.MAX_VALUE;
            // 如果当前金额等于 i = 8, 从 memo[7],memo[6],memo[3] 中获取最小值
            // u = 1, memo[7]=memo[i-u]
            // u = 2, memo[6]=memo[i-u]
            // u = 5, memo[3]=memo[i-u]
            for(int j = 0;j < coins.length;j++){
                if(i - coins[j] >= 0 && memo[i-coins[j]] < min){
                    min = memo[i-coins[j]] + 1;
                }
            }
            // memo[i] = (min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min);
            memo[i] = min;
        }
        return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
    }
}
